1538E - Funny Substrings - CodeForces Solution

import re
import sys
input = sys.stdin.readline
t = int(input())


class Node():
    def __init__(self, p, s, cnt, size):
        self.p = p
        self.s = s
        self.cnt = cnt
        self.size = size

    @classmethod
    def fromString(cls, s):
        return cls(s[:3], s[-3:], cls.count(s), len(s))

    @classmethod
    def merge(cls, a, b):
        p = a.p if a.size >= 3 else (a.p+b.p)[:3]
        s = b.s if b.size >= 3 else (a.s + b.s)[-3:]
        return cls(p, s, a.cnt + b.cnt + cls.count(a.s + b.p), a.size + b.size)

    @staticmethod
    def count(s):
        return sum(s[i:i+4] == "haha" for i in range(len(s) - 3))


def getList():
    return map(int, input().split())


def solve():
    q = int(input())
    w = {}
    for _ in range(q):
        s = input().rstrip()
        if ":" in s:
            a, b = s.split(" := ")
            w[a] = Node.fromString(b)
        else:
            a, b, c = re.split(r"\W+", s)
            w[a] = Node.merge(w[b], w[c])
    print(w[a].cnt)


for _ in range(t):
    solve()